package leetcode;

import java.util.*;

public class LC12 {
    public static void main(String[] args) {
        LC12 lc12 = new LC12();
        System.out.println(lc12.minWindow1("a", "aa"));
        System.out.println(lc12.minWindow1("a", "a"));
        System.out.println(lc12.minWindow1("ADOBECODEBANC", "ABC"));
    }

    int id(char c) {
        return c >= 'a' && c <= 'z' ? c - 'a' : c - 'A' + 26;
    }

    public String minWindow1(String s, String t) {
        int[] mp = new int[52];
        int less = 0;
        for (char c : t.toCharArray())
            if (--mp[id(c)] == -1) ++less;
        int i = 0, j = 0;
        int start = 0, len = Integer.MAX_VALUE;
        while (j < s.length()) {
            if (++mp[id(s.charAt(j))] == 0 && --less == 0) {
                while (i <= j)
                    if (--mp[id(s.charAt(i++))] == -1){
                        ++less;
                        break;
                    }
                if (j - i + 2 < len) {
                    start = i - 1;
                    len = j - i + 2;
                }
            }
            ++j;
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> tmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i), 0) + 1);
        }
        Map<Character, Integer> smap = new HashMap<>();
        int sl = 0, sr = 0;
        int ansL = -1, ansR = s.length();
        for (sr = 0; sr < s.length(); sr++) {
            char x = s.charAt(sr);
            smap.put(x, smap.getOrDefault(x, 0) + 1);
            while (check(smap, tmap) && sl <= sr) {
                if (ansR - ansL > sr - sl) {
                    ansR = sr + 1;
                    ansL = sl;
                }
                smap.put(s.charAt(sl), smap.get(s.charAt(sl)) - 1);
                sl++;
            }
        }
        System.out.println(smap);
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    private boolean check(Map<Character, Integer> ss, Map<Character, Integer> tt) {
        for (Map.Entry<Character, Integer> en : tt.entrySet()) {
            if (en.getValue() > ss.getOrDefault(en.getKey(), 0)) return false;
        }
        return true;
    }
}
